''' 这个过程没办法一步一步理解，记住它的格式就好！！！！

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
输入：n = 4, k = 2
输出：
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

链接：https://leetcode.cn/problems/combinations
'''

# 排列组合的性质C(n,m)=C(n-1,m)+C(n-1,m-1) # 从n个数中取m个数进行组合
class Solution(object):
    def combine(self, n, k):
        if k> n or k == 0:
            return []
        if k == 1:
            return [[i] for i in range(1, n + 1)]
        if k == n:
            return [[i for i in range(1, n + 1)]]

        answer = self.combine(n - 1, k)  # 直接获取 C(n-1,m)项
        # print(answer)
        for item in self.combine(n - 1, k - 1): # 开始计算C(n-1,m-1)项
            # print(item)
            item.append(n) # 因为k-1导致维度小了，需要补一个缩小维度后取不到的值
            answer.append(item) # 把C(n-1,m-1)项 一个一个成员加进去C(n,m)

        # answer.sort(key=lambda x:x[0])
        return answer

s = Solution()
print(s.combine(10,2))







